// 分隔链表

package Leetcode;

/**
 * Definition for singly-linked list.
 * public class ListNode {
 * int val;
 * ListNode next;
 * ListNode() {}
 * ListNode(int val) { this.val = val; }
 * ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */

class solution_086 {
    public ListNode partition(ListNode head, int x) {
        ListNode pre = new ListNode();
        ListNode slow = new ListNode();
        ListNode fast = new ListNode();
        // 剪枝
        if (head == null)
            return head;
        // 如果第一个值应该在结果中则直接纳入否则链表会出现循环
        // if (head.val >= x) {
        slow.next = head;
        fast.next = head;
        pre = slow;
        // } else {
        // slow = head;
        // fast = head;
        // pre.next = slow;
        // }
        // System.out.println(slow.next == fast.next);
        while (fast != null) {
            // 调整相应的链表
            if (fast.next != null && fast.next.val < x) {
                // 如果slow和fast位置相同，则直接后移
                if (slow.next == fast.next) {
                    slow = slow.next;
                    fast = fast.next;
                } else { // 否则就改变指针的指向
                    ListNode fn = fast.next;
                    fast.next = fn.next;
                    fn.next = slow.next;
                    slow.next = fn;
                    // slow后移，fast不用，因为fast.next后续值已经改变
                    slow = slow.next;
                }

            } else {
                fast = fast.next;
            }
        }
        return pre.next;
    }

    public static void main(String[] args) {
        solution_086 s = new solution_086();
        ListNode head = new ListNode(1);
        // ListNode node1 = new ListNode(2);
        int x = 0;
        s.partition(head, x);
    }
}

public class Solution086 {

}
